package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.BinaryTreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 从上到下打印二叉树
 *
 * @author yuhushuan
 * @date 2020/6/21 02:20
 */
public class _32_1_PrintTreeFromTopToBottom {

    private static void printFromTopToBottom(BinaryTreeNode root){
        if (root == null){
            System.out.println("null");
            return;
        }
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        queue.add(root);
        BinaryTreeNode node;
        while (!queue.isEmpty()){
            node = queue.poll();
            System.out.print(node.value + " ");

            if (node.left != null){
                queue.add(node.left);
            }
            if (node.right != null){
                queue.add(node.right);
            }
        }
        System.out.println();
    }

    private static void level(BinaryTreeNode root) {
        if (root == null) {
            System.out.println("null");
            return;
        }
        Queue<BinaryTreeNode> queue1 = new LinkedList<>();
        Queue<BinaryTreeNode> queue2 = new LinkedList<>();

        queue1.add(root);

        BinaryTreeNode node;
        while (!queue1.isEmpty() || !queue2.isEmpty()) {
            while (!queue1.isEmpty()) {
                node = queue1.poll();
                System.out.print(node.value + " ");
                if (node.left != null) {
                    queue2.add(node.left);
                }
                if (node.right != null) {
                    queue2.add(node.right);
                }
            }
            System.out.println();
            while (!queue2.isEmpty()) {
                node = queue2.poll();
                System.out.print(node.value + " ");
                if (node.left != null) {
                    queue1.add(node.left);
                }
                if (node.right != null) {
                    queue1.add(node.right);
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // 功能测试
        // 完全二叉树
        print(getTest1());
        // 所有节点只有左子树的二叉树
        print(getTest2());
        // 所有节点只有右子树的二叉树
        print(getTest3());

        // 特殊输入测试
        // 根节点为null
        print(null);
        // 只有一个节点
        print(new BinaryTreeNode(1));
    }

    private static void print(BinaryTreeNode root){
        System.out.println("二叉树：");
        BinaryTreeNode.drawBinaryTree(root);
        System.out.println("从上到下打印：");
        printFromTopToBottom(root);
        System.out.println("层级遍历：");
        level(root);
        System.out.println();
    }

    private static BinaryTreeNode getTest1() {
        // [1, 2, 4, 7, 3, 5, 6, 8]
        BinaryTreeNode[] nodes = new BinaryTreeNode[9];
        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = new BinaryTreeNode();
            nodes[i].value = i;
        }

        BinaryTreeNode root = nodes[1];

        nodes[1].left = nodes[2];
        nodes[1].right = nodes[3];

        nodes[2].left = nodes[4];
        nodes[2].right = nodes[5];

        nodes[3].left = nodes[6];
        nodes[3].right = nodes[7];
        return root;
    }

    private static BinaryTreeNode getTest2() {
        // [1, 2, 4, 7, 3, 5, 6, 8]
        BinaryTreeNode[] nodes = new BinaryTreeNode[9];
        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = new BinaryTreeNode();
            nodes[i].value = i;
        }

        BinaryTreeNode root = nodes[1];

        nodes[1].left = nodes[2];
        nodes[2].left = nodes[3];
        nodes[3].left = nodes[4];
        nodes[4].left = nodes[5];
        nodes[5].left = nodes[6];
        nodes[6].left = nodes[7];
        return root;
    }

    private static BinaryTreeNode getTest3() {
        // [1, 2, 4, 7, 3, 5, 6, 8]
        BinaryTreeNode[] nodes = new BinaryTreeNode[9];
        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = new BinaryTreeNode();
            nodes[i].value = i;
        }

        BinaryTreeNode root = nodes[1];

        nodes[1].right = nodes[2];
        nodes[2].right = nodes[3];
        nodes[3].right = nodes[4];
        nodes[4].right = nodes[5];
        nodes[5].right = nodes[6];
        nodes[6].right = nodes[7];
        return root;
    }
}
